package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MergeIntervals56 {
    public int[][] merge(int[][] v) {
        if (v == null || v.length == 1) {
            return v;
        }

        Arrays.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        List<int[]> list = new ArrayList<>(v.length);
        int[] curr = v[0];
        for (int i = 1; i < v.length; i++) {
            if (v[i][0] <= curr[1]) {
                curr[1] = Math.max(v[i][1], curr[1]);
            } else {
                list.add(curr);
                curr = v[i];
            }
        }
        list.add(curr);
        return list.toArray(new int[0][0]);
    }
}
